# 动态规划设计之最长递增子序列

def length_of_lis(nums: list[int]):
    # dp数组都初始化为1
    dp = [1 for i in range(0, len(nums))]
    # 动态规划计算 dp[i]的每一个值
    for i in range(0, len(nums), 1):
        # print(nums[i])
        # 遍历查找比i小的dp table
        for j in range(0, i, 1):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    res = 0
    for i, v in enumerate(dp):
        res = max(res, v)
    return res


if __name__ == '__main__':
    print('start')
    a = [10, 9, 2, 5, 3, 7, 101, 18]
    res = length_of_lis(a)
    print(res)
